package day03;

/**
 * 给定一个包含n + 1 个整数的数组nums ，其数字都在[1, n]范围内（包括 1 和 n），可知至少存在一个重复的整数。
 *
 * 假设 nums 只有 一个重复的整数 ，返回这个重复的数 。
 *
 * 你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。
 *
 *
 *
 * 示例 1：
 *
 * 输入：nums = [1,3,4,2,2]
 * 输出：2
 * 示例 2：
 *
 * 输入：nums = [3,1,3,4,2]
 * 输出：3
 *
 *
 */
public class Solution4 {
    public int findDuplicate(int[] nums) {
        int left = 1,right = nums.length;
        while (left<right){
            int mid = (right-left)/2 +left;
            int count = 0;
            for (int i = 0; i <nums.length; i++) {
                if(nums[i]<=nums[mid]){
                    count++;
                }
            }
            if(count>mid){
                right = mid;
            }else {
                left = mid+1;
            }
        }
        return right;
    }
}
